package C060;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c02
 * Package: C060
 * Description:
 // 喧闹和富有
 // 从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值
 // 给你一个数组richer，其中richer[i] = [ai, bi] 表示
 // person ai 比 person bi 更有钱
 // 还有一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值
 // richer 中所给出的数据 逻辑自洽
 // 也就是说，在 person x 比 person y 更有钱的同时，不会出现
 // person y 比 person x 更有钱的情况
 // 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是,
 // 在所有拥有的钱肯定不少于 person x 的人中，
 // person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
 // 测试链接 : https://leetcode.cn/problems/loud-and-rich/
 * @Author BCXJ
 * @Create 2025/11/26 17:45
 * @Version 1.0
 * @Since 1.0
 */
public class c02 {
    static int N  =500;
    static List<List<Integer>> graph = new ArrayList<>(N);
    static {
        for (int i = 0; i < 500; i++) {
            graph.add(new ArrayList<>());
        }
    }

    static int n; // 案例的节点数
    static int[] indegree = new int[N];

    static int[] queue = new int[N];
    static int l = 0, r = 0;

    // 使用邻接表的方式进行
    // richer 0 -> 1
    public static int[] loudAndRich(int[][] richer, int[] quiet) {
        // 初始化
        n = quiet.length;
        for (int i = 0; i < n; i++) {
            graph.get(i).clear();
        }
        Arrays.fill(indegree, 0);

        // 建立表，初始化入度表
        for (int i = 0; i < richer.length; i++) {
            graph.get(richer[i][0]).add(richer[i][1]);
            indegree[richer[i][1]]++;
        }

        // 入度为0的入队列
        l = r = 0;
        for (int i = 0; i < n; i++) {
            if(indegree[i] == 0) {
                queue[r ++] = i;
            }
        }
        int[] ans = new int[n];
        // 自己就是最安静的（比自己有钱的人中）
        for (int i = 0; i < ans.length; i++) {
            ans[i] = i;
        }

        // 拓扑排序获取结果
        while(l < r) {
            int curNode = queue[l ++];
            for (int next : graph.get(curNode)) {
                indegree[next]--;
                if(quiet[ans[next]] > quiet[ans[curNode]]) {
                    ans[next] = ans[curNode];
                }
                if(indegree[next] == 0) {
                    queue[r ++] = next;
                }
            }
        }


        return ans;
    }


    public static void main(String[] args) {
        int[][] arr = {{1,0},{2,1},{3,1},{3,7},{4,3},{5,3},{6,3}};
        int[] arr2 = {3,2,5,4,6,1,7,0};

        System.out.println(Arrays.toString(loudAndRich(arr, arr2)));
        System.out.println(Arrays.toString(loudAndRich(arr, arr2)));

    }
}
